Search results for "Routing problems with profits"

showing 2 items of 2 documents

A branch-and-cut algorithm for the Orienteering Arc Routing Problem

2016

[EN] In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP),in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route.In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds…

Mathematical optimization021103 operations researchGeneral Computer Science0211 other engineering and technologiesOrienteering02 engineering and technologyManagement Science and Operations ResearchTime limitRouting problems with profitsPolyhedronExact algorithmOrienteering Arc Routing ProblemBranch-and-cutModeling and Simulation0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingDestination-Sequenced Distance Vector routingMATEMATICA APLICADAInteger programmingArc routingAlgorithmBranch and cutMathematicsComputers & Operations Research
researchProduct

A matheuristic for the Team Orienteering Arc Routing Problem

2015

In the Team OrienteeringArc Routing Problem (TOARP) the potential customers are located on the arcs of a directed graph and are to be chosen on the basis of an associated profit. A limited fleet of vehicles is available to serve the chosen customers. Each vehicle has to satisfy a maximum route duration constraint. The goal is to maximize the profit of the served customers. We propose a matheuristic for the TOARP and test it on a set of benchmark instances for which the optimal solution or an upper bound is known. The matheuristic finds the optimal solutions on all, except one, instances of one of the four classes of tested instances (with up to 27 vertices and 296 arcs). The average error o…

MatheuristicMathematical optimizationInformation Systems and ManagementGeneral Computer ScienceComputer scienceOrienteeringDirected graphManagement Science and Operations ResearchUpper and lower boundsIndustrial and Manufacturing EngineeringVertex (geometry)Constraint (information theory)Set (abstract data type)Routing problems with profitsArc routing problemModeling and SimulationBenchmark (computing)Team Orienteering ProblemDuration (project management)MATEMATICA APLICADAArc routing
researchProduct